#include <vector>
#include <set>
#include <map>
#include <random>
#include <limits>
#include <Rcpp.h>
using namespace Rcpp;


typedef std::vector<std::vector<int>> Tree;
typedef std::vector<std::vector<int>> Graph;
typedef std::vector<std::vector<std::vector<int>>> Multigraph;

std::random_device rd;
std::mt19937 generator(rd());
std::uniform_real_distribution<double> unif(0.0, 1.0);

/*
 * Generate a uniform random integer in [0, max).
 */
inline int rint(int max) {
    return std::floor(max * unif(generator));
}

/*
 * Generate a random vertex (integer) among unvisited vertices
 */
// TESTED
inline int rvtx(const std::vector<bool> &visited, int size, int remaining) {
    int idx = rint(remaining);
    int accuml = 0;
    for (int i = 0; i < size - 1; i++) {
        accuml += 1 - visited.at(i);
        if (accuml - 1 == idx) return i;
    }
    return size - 1;
}

/*
 * Generate a random neighbor to a vertex, except for the `last` vertex.
 */
// TESTED
inline int rnbor(const Graph &g, int vtx) {
    int n_nbors = g.at(vtx).size();
    return g[vtx][rint(n_nbors)];
}


/*
 * Convert R adjacency list to Graph object (vector of vectors of ints).
 */
inline Graph list_to_graph(const List &l) {
    int V = l.size();
    Graph g;
    for (int i = 0; i < V; i++) {
        g.push_back(as<std::vector<int>>((IntegerVector) l[i]));
    }
    return g;
}

template<typename T>
inline void print_vec(std::vector<T> x) {
    int n = x.size();
    for (int i = 0; i < n; i++) {
        Rcout << x[i] << " ";
    }
    Rcout << "\n";
}

